package com.suanfa.tianxun;

import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * @author tianxun
 * @date 2023/12/20 14:26
 * @desc
 */
public class 广度优先 {
    public static void main(String[] args) {
        Node firstNode = new Node();
        firstNode.name = "Alice";

        Node secondNode = new Node();
        secondNode.name = "Bob";

        Node thirdNode = new Node();
        thirdNode.name = "Cat";

        Node forthNode = new Node();
        forthNode.name = "Dad";

        Node fifthNode = new Node();
        fifthNode.name = "Ella";

        Node sixthNode = new Node();
        sixthNode.name = "Fake";

        List<Node> firstNodeList = new ArrayList<>();
        firstNodeList.add(secondNode);firstNodeList.add(forthNode);
        firstNode.nodeList = firstNodeList;

        List<Node> secondNodeList = new ArrayList<>();
        secondNodeList.add(thirdNode);secondNodeList.add(forthNode);
        secondNode.nodeList = secondNodeList;

        List<Node> thirdNodeList = new ArrayList<>();
        thirdNodeList.add(fifthNode);thirdNodeList.add(forthNode);thirdNodeList.add(sixthNode);
        thirdNode.nodeList = thirdNodeList;

        List<Node> forthNodeList = new ArrayList<>();
        forthNodeList.add(fifthNode);
        forthNode.nodeList = forthNodeList;

        List<Node> fifthNodeList = new ArrayList<>();
        fifthNodeList.add(sixthNode);
        fifthNode.nodeList = fifthNodeList;

        List<Node> sixthNodeList = new ArrayList<>();
        sixthNode.nodeList = sixthNodeList;
        test("Faker",firstNode);
    }

    private static void test(String name,Node firstNode) {
        LinkedBlockingDeque<Node> nodeQueue = new LinkedBlockingDeque<>();//存放待检查的节点
        Set<String> checkedSet = new HashSet<>();//存放已经检查过的节点
        nodeQueue.add(firstNode);
        while(!nodeQueue.isEmpty()){
            Node poll = nodeQueue.poll();
            List<Node> nodeList = poll.nodeList;
            for (Node node : nodeList) {
                if(name.equals(node.name)){
                    System.out.println("找到了目标节点"+name);
                    return;
                }else if(!checkedSet.contains(node.name)){
                  checkedSet.add(node.name);
                  nodeQueue.add(node);
                }
            }
        }
        System.out.println("所有节点已找完，未找到目标节点"+name);
    }
}
